In practice, except for the most basic systems, mathematical models for dynamic systems involve a complex set of mathematical transformations applied in some prescribed manner with the outputs of some transformations forming the inputs of others. Each elemental transformation may be viewed in isolation as a simple dynamic system. Therefore, a complex dynamic system may be modeled as an interconnection of various simple dynamic systems. A schematic representation of such an interconnection that has evolved over the years is the block diagram. Such block diagram models have now become a standard means in textbooks, design papers, journal articles, and specifications to communicate the details of a dynamic system's behavior.
A block diagram model of a dynamic system is represented schematically as a collection of blocks interconnected by lines that represent signals. A signal represents the input and output of a dynamic system. Each block represents an elemental dynamic system. A line emanating at one block and terminating at another signifies that the output of the first block is an input to the second block. Each distinct input or output on a block is referred to as a port. Signals correspond to the time-varying quantities represented by each line connection and are assumed to have values at each time instant. The source block of a signal writes to the signal at a given time instant when its system equations are solved. The destination blocks of this signal read from the signal when their system equations are being solved. The block diagram includes a plurality of blocks, lines and ports that are interconnected. Those skilled in the art will recognize that the term “blocks” does not refer exclusively to elemental dynamic systems but may also include other modeling elements that aid in readability and modularity of block diagrams.
Block diagram models are time-based relationships between signals and state variables representative of a dynamic system. The solution (computation of system response) of the model is obtained by evaluating these relationships over time, where time starts at a user-specified “start time” and either ends at a user-specified “stop time” or based on evaluating a criterion that may involved model quantities. At each time step these relationships are evaluated. Signals represent quantities that change over time, and these quantities are defined for all points in time between the block diagram's start and stop time. The relationships between signals and state variables are defined by sets of equations represented by blocks. These equations define a relationship between the input signals, output signals, state, and time.
The block diagrams are not exclusively used for representing time-based dynamic systems but also for other models of computation. For instance, flow-charts are block diagrams used to capture process flow and are not generally suitable for describing dynamic system behavior. Data flow block diagrams are block diagrams that describe a graphical programming paradigm where the availability of data (often thought of as tokens) is used to initiate the execution of blocks, where a block represents an operation and a line represents execution dependency describing the direction of data flowing between blocks.
Inherent in the various classes of dynamic systems is the notion of system sample time. The sample-time is the time interval at which the inputs, state, or outputs (collectively referred to as the results) of the systems are traced as time progresses. If a system has only one sample time, it is said to be single-rate. If a system has multiple sample times, it is said to be multi-rate. Multi-rate systems can be evaluated (executed) using either a single-tasking form of execution or a multi-tasking form of execution.
FIG. 1A shows an exemplary task execution profile of the single-rate execution scheme. In the single-rate execution scheme, a block diagram has a single sample time 1000 and runs at every sample hit (triangle) 1010. The execution of the block diagram at each sample hit is depicted as a bar 1020. As long as all the elements of the block diagram can be executed before the next sample hit, no scheduling problem occurs. When a block diagram has multiple rates, different portions of the block diagram must be run at different sample times. The simplest approach for executing a multi-rate block diagram is to use a single-tasking scheduler.
FIG. 1B shows an exemplary task execution profile of the multi-rate, single-tasking execution scheme. In this example, the block diagram has two separate sample rates. The portions of the block diagram that are associated with a base rate are executed at every sample hit. However, the portions of the block diagram that are associated with a sub-rate execute at every fourth sample hit 1030. That is, the task execution that begins at every fourth sample hit 1030 executes the portions of the block diagram that are associated with both sample rates. In this situation, the multi-rate single-tasking scheduler executes the block diagram in the manner illustrated in FIG. 1A, but enables the execution of the block diagram at multi-rates by selecting the executions, as shown below in the following pseudo code example.
main_task( ) {execute fastest blocksif (time == slow rate sample hit){execute slower blocks}}
FIG. 1C shows an exemplary task execution profile of a priority-based multi-rate, multi-tasking execution scheme. A priority-based multi-tasking scheduler is the most efficient method for executing a multi-rate system. The multi-tasking scheduler may be based on a real-time operating system (RTOS) or implemented directly as a timer interrupt service routine for the target hardware. For optimal execution, the separate tasks may be prioritized in a rate-monotonic order, from the fastest task to the slowest task. A multi-tasking scheduler allows a lower priority (longer sample time) task to be pre-empted by a higher priority (shorter sample time) task. The areas 1040-1043 in FIG. 1C correspond to task preemption, meaning that task execution is suspended by the interrupt request of a higher priority task. This process may occur on multiple levels. FIG. 1C shows an instance in which the lowest priority task (Sub-Rate 2) 1050 waits on the mid-priority task (Sub-Rate 1) 1060, which in turn is waiting on the highest priority task (Base-Rate) 1070.
The scheduling schemes described above with reference to FIGS. 1A-1C may be applied to applications where the algorithm has been specified using a block diagram modeling environment and the real-time implementation of this algorithm has been created using automatic code generation. In such cases it is possible to simulate the behavior of the algorithm using the block diagram modeling environment. In particular, the block diagram modeling environment can be configured such that the simulation results reproduce the effect of the real-time scheduler's mode of operation. For example, an algorithm that is configured to run in a single-tasking execution environment may behave differently to the same algorithm when it is configured to run in a multi-tasking environment.
Conventional scheduling schemes work when a processor is nominally loaded, but may fail if the processor becomes overloaded. When a task is required to perform extra processing and takes longer than normal to execute, it may be scheduled to execute before a previous instance of the same task has completed. This is referred to as a task overrun. On occurrence and detection of a task overrun, the scheduler must take appropriate action. For example, one possible course of action is to record that a failure has occurred and reset the application. Alternatively, it is possible to implement a less drastic course of action that does not force a reset of the real-time system and allows operation to continue, for example, to skip execution of the task that is scheduled to execute before the previous instance is complete.